package bintree.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: yuisama
 * @Date: 2021/9/9 15:52
 * @Description:根据中序和后序遍历结果构建二叉树
 * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 */
public class Num106_BuildTreeByInAndPostOrder {
    /**
     * 二叉树的后序遍历结果反转就是二叉树前序遍历结果的镜像(根右左)
     * @param inorder
     * @param postorder
     * @return
     */
    private int index;
    private Map<Integer,Integer> valueMap = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // 1.反转后序遍历数组得到前序结果的镜像,同时在哈希表中存储中序节点的元素值以及对应下标
        int[] preOrder = reverseNum(postorder,inorder);
        // 2.递归处理前右左树，问题转化为根据中序和后序构建二叉树问题
        return buildTreeHelper(preOrder,postorder,0,preOrder.length);
    }

    private TreeNode buildTreeHelper(int[] preOrder, int[] postorder, int left, int right) {
        // 子树为空，结束递归
        if (left >= right)
            return null;
        // 前序集合遍历完毕，递归结束
        if (index >= preOrder.length)
            return null;
        // 在前序遍历中取出根节点
        TreeNode root = new TreeNode(preOrder[index]);
        index ++;
        // 找到根节点在中序遍历中位置索引
        int pos = valueMap.get(root.val);
        // 继续处理右子树(前序遍历镜像结果为根右左，因此先处理右子树)
        root.right = buildTreeHelper(preOrder,postorder,pos + 1,right);
        root.left = buildTreeHelper(preOrder,postorder,left,pos);
        return root;
    }

    /**
     * 将给定数组逆置处理
     * @param arr
     * @return
     */
    private int[] reverseNum(int[] arr,int[] inOrder) {
        int[] result = new int[arr.length];
        int j = arr.length - 1;
        for (int i = 0; i < arr.length; i++) {
            result[i] = arr[j];
            j--;
        }
        // 遍历中序遍历结果并将元素存储在哈希表
        for (int i = 0; i < inOrder.length; i++) {
            valueMap.put(inOrder[i],i);
        }
        return result;
    }
}
